package bit_pratice.day11;

/**
 * 将一棵无穷大满二叉树的结点按根结点一层一层地从左往右编号，根结点编号为1。
 * 现给定a，b为两个结点。设计一个算法，返回a、b最近的公共祖先的编号。注意其祖先也可能是结点本身。
 **/
public class 最近公共祖先 {
    public int getLCA(int a, int b) {
        //方法1
        //parent=较大child/2，最后两个child值相等时那个等值就是最近公共祖先
        while (a!=b){
            if(a>b){
                a=a/2;
            }else {
                b=b/2;
            }

        }
        return a;//没有的话÷到最后a值是0
    }
}
///**
// * 找到最近公共祖先
// * 给定一个二叉树，找到两个指定节点的最近公共祖先
// */
//public class Num236_NearestCommonAncestor {
//    //最近公共祖先
//    private TreeNode nca;
//    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//        //题目给出的条件可知无需判空
//        //findNode找到p或q的祖先,在其中顺便找了公共祖先
//        findNode(root,p,q);
//        return nca;
//    }
//
//    /**
//     * 以当前root为根节点的二叉树是否能找到p或q
//     * findNode方法不是找公共祖先的方法，只是判断当前树是否是p或q的祖先，找到一个就说明至少是一个结点的祖先
//     * 只是找是否是p或q的祖先的过程中判断了是否是公共祖先
//     * @param root
//     * @param p
//     * @param q
//     */
//    private boolean findNode(TreeNode root, TreeNode p, TreeNode q) {
//        if(root==null){
//            return false;
//        }
//        //用整型变量记录是否找到节点
//        //先在左子树中找p或q
//        //若left==1，说明左树至少找到了一个p或q
//        int left=findNode(root.left,p,q)?1:0;
//        //再在右子树中找p或q
//        //若right==1，说明右树至少找到了一个p或q
//        int right=findNode(root.right,p,q)?1:0;
//        //最后在根节点下判断根节点是否是p或q
//        //mid==1，说明根节点就是p或q
//        int mid=(root==p||root==q)?1:0;
//        if(left+right+mid==2){
//            //相加和为2，根节点就是最近公共祖先
//            nca=root;
//        }
//        //否则，有没有祖先就是看就是看上面有没有大于零的数
//        return (left+right+mid)>0;
//    }
//}